package StackOrQueue;//给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
//。 
//
// 返回滑动窗口中的最大值。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//输出：[3,3,5,5,6,7]
//解释：
//滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3
// 1 [3  -1  -3] 5  3  6  7       3
// 1  3 [-1  -3  5] 3  6  7       5
// 1  3  -1 [-3  5  3] 6  7       5
// 1  3  -1  -3 [5  3  6] 7       6
// 1  3  -1  -3  5 [3  6  7]      7
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], k = 1
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,-1], k = 1
//输出：[1,-1]
// 
//
// 示例 4： 
//
// 
//输入：nums = [9,11], k = 2
//输出：[11]
// 
//
// 示例 5： 
//
// 
//输入：nums = [4,-2], k = 2
//输出：[4] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -10⁴ <= nums[i] <= 10⁴ 
// 1 <= k <= nums.length 
// 
// Related Topics 队列 数组 滑动窗口 单调队列 堆（优先队列） 👍 1248 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    static class MyQueue{
        Queue<Integer> queue;

        public MyQueue(){
            //初始化
            queue = new LinkedList<>();
        }
        public void pop(int value){
            // 删除滑动窗口要移出去的元素
            Stack<Integer> helper = new Stack<>(); //辅助栈
            while(!queue.isEmpty()){
                int curr = queue.poll();
                if(curr != value){
                    //当前弹出的不是目标值，加入辅助栈
                    helper.push(curr);
                }else if(!helper.isEmpty()){
                    // 如果找到了目标值，且辅助栈不为空，将辅助栈的值移回原始队列
                    while (!helper.isEmpty()){
                        push(helper.pop());
                    }
                    //移动完成，直接结束
                    break;
                }else{
                    // 第一个值即目标值，弹完即结束
                    break;
                }
            }

        }
        public void push(int value){
            // 添加滑动窗口要移进来的元素并保证满足单调队列
            Queue<Integer> queue1 = new LinkedList<>(); //辅助队列
            if (queue.isEmpty()){
                queue.offer(value);
                return;
            }
            boolean flag = false;
            while(!queue.isEmpty()){
                if(value <= queue.peek()){
                    //如果添加的值小于当前队列中头部最大的值
                    //则将头部加入辅助队列
                    queue1.add(queue.poll());
                }else {
                    queue1.add(value);
                    flag = true;
                    break;
                }
            }
            //如果添加元素是窗口中的最小元素，则需要最后添加
            if (!flag){
                queue1.offer(value);
            }
            while(!queue.isEmpty()){
                queue1.offer(queue.poll());
            }
            queue = queue1;
        }
        public Integer front(){
            //获得队列最前面的 即最大值
            return queue.peek();
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        System.out.println();
    }


}
//leetcode submit region end(Prohibit modification and deletion)
